#include <bits/stdc++.h>
using namespace std;

/*
1493. 删掉一个元素以后全为 1 的最长子数组
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

 

提示 1：

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。
示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。
示例 3：

输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。
 

提示：

1 <= nums.length <= 105
nums[i] 要么是 0 要么是 1 。
*/

// 法一
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        // dp + 滑动窗口
        int left = 0;
        int zerCnt = 0;
        int maxLen = 0;
        int n = nums.size();

        // 右指针遍历 扩展窗口
        for (int right = 0; right < n; right++) {
            // 遇0就更新cnt
            if (nums[right] == 0)   zerCnt++;

            //cnt >=  1 左边窗口收缩
            while (zerCnt > 1) {
                // 左边界是0 要减少0cnt
                if (nums[left] == 0)   zerCnt--;
                left++;
            }
            // 遍历完了就知道最大长度 
            maxLen = max(maxLen, right - left);
        }
        return maxLen;
    }
};

// 法二
// 优化的滑动窗口
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int res = 0;          // 存储最终结果：删除一个元素后最长全1子数组的长度
        int l = 0, r = 0;     // 滑动窗口的左右指针，[l, r]为当前窗口范围
        int len = 0;          // 当前窗口的长度（r - l + 1的实时记录）
        int sum = 0;          // 当前窗口中1的总和（因数组是二进制，sum即1的数量）
        
        // 右指针遍历数组，不断扩展窗口
        for (r = 0; r < nums.size(); r++) {
            sum += nums[r];   // 累加当前元素（1则加1，0则加0，统计窗口内1的总数）
            len++;            // 窗口长度+1（右指针右移，窗口扩大）           
            // 核心逻辑：保证窗口内0的数量不超过1（0的数量 = 窗口长度 - 1的数量）
            // 当0的数量>1时，收缩左指针，直到0的数量≤1
            while (len - sum > 1) {
                sum -= nums[l];  // 左指针元素移出窗口，减去其值（1则减1，0则减0）
                len--;           // 窗口长度-1（左指针右移，窗口缩小）
                l++;             // 左指针右移
            }
            // 更新最大长度：当前窗口中1的数量就是删除一个0后的有效长度（若有0）
            res = max(res, sum);
        }
        
        // 特殊情况：若原数组全是1（sum等于数组长度），必须删除一个元素，因此结果减1
        if (res == nums.size()) {
            res--;
        }
        
        return res;
    }
};

// 法三
// 稍微暴力点的方式
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int prev = 0;       // 记录前一段连续1的长度（与当前段之间可能隔1个0）
        int last = 0;       // 记录当前段连续1的长度
        bool islast = false;// 标记是否处于当前连续1的段（用于区分prev和last）
        int sum = 0;        // 存储最大长度结果
        int zeros = 0;      // 记录当前统计区间内0的数量
        int allzero = 0;    // 统计数组中0的总数量（用于判断全为1的特殊情况）
        
        for (auto num : nums) {
            if (num == 1) {
                // 处理1的情况：根据当前状态更新prev或last
                if (!islast && zeros == 0) {
                    prev++;  // 无0且不在当前段，累加前序1
                } else if (!islast && zeros == 1) {
                    last++;  // 有1个0且不在当前段，开始累加当前段1
                    islast = true;
                } else if (!islast && zeros > 1) {
                    sum = max(prev, sum);  // 0超过1个，更新最大长度，重置前序1
                    prev = 0;
                } else {
                    last++;  // 在当前段，继续累加
                }
            } else {
                // 处理0的情况：更新计数并根据状态合并片段
                allzero++;
                if (islast) {
                    sum = max(prev + last, sum);  // 处于当前段，合并前后1段（删除中间0）
                    prev = last;  // 当前段转为前序段
                    last = 0;
                    zeros = 0;
                } else {
                    sum = max(prev, sum);  // 不处于当前段，更新最大长度
                    if (prev != 0) zeros++;  // 前序有1时，0计数+1
                    if (zeros > 1) {  // 0超过1个，重置前序1和0计数
                        prev = 0;
                        zeros = 0;
                    }
                }
            }
        }
        sum = max(prev + last, sum);  // 循环结束后，最后一次合并判断
        
        // 全为1时需删除一个，否则直接返回sum
        return allzero == 0 ? sum - 1 : sum;
    }
};